#include<iostream>
#include<vector>
using namespace std;
//下标为元素的编号，每一个集合的根节点的值都是负数,数值表示该集合的元素个数
//如果数组中某个值为正数，则代表其父节点在该下标
// _set[x]<0 :说明x是集合的根节点,该集合的元素个数为_set[x]个,
// _set[x] >0 :说明x的父亲节点在数组的_set[x]下标位置
class UnionFindSet
{
public:
    UnionFindSet(size_t n)
    {
    	_set.resize(n,-1);//最初每个元素自成一个集合
	}
	
	//普通版本
  size_t FindRoot(int x)
  {
      size_t root = x;
      while(_set[root] >= 0)
      {
        root = _set[root];//去其父节点的位置
      }
	  //压缩路径，帮沿途的节点父节点都改为root
	  while(_set[x] >= 0)
	  {
		int parent = _set[x];//先保存其父节点的下标
		_set[x] = root;
		x = parent;//去其父节点位置
	  }
      return root;
  }
	
	
	//将x2合并到x1的集合当中
    void Union(int x1, int x2)
    {
	  size_t root1 = FindRoot(x1);
      size_t root2 = FindRoot(x2);
      if(root1 != root2)
      {
		//压缩:因为把x2合并到x1的集合当中，所以如果x2更大(集合元素更多)的话，那么就反过来
		//因为根节点对应的值为负数，代表的是集合中元素个数, _set[root1]  > _set[root2]说明root2集合的元素个数更多
		if(_set[root1]  > _set[root2]) 
		{
			//Union(x2,x1);
			//或者写为:
			swap(root1,root2);
		}
        _set[root1] += _set[root2];
        _set[root2] = root1;
      }
    }
    bool Inset(int x1,int x2)
    {
    	return FindRoot(x1) == FindRoot(x2);
	}
	
	//统计集合个数 ==> 判断数组有多少个元素是<0的
    size_t SetCount()
    {
    	size_t count = 0;
    	for(auto& x: _set)
    	{
    		if(x < 0)
    		{
    			count++;
			}
		}
		return count;
	}
private:
	std::vector<int> _set;
};
